class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        int l = 1, r = x;
        int mid;
        while(l < r) {
            mid = l + (r-l)/2;
            if(mid < x/mid)
                l = mid + 1;
            else if(mid == x/mid)
                return mid;
            else
                r = mid;
        }
        if(l > x/l)
            l--;
        return l;
    }
    /*int sqrt(int x) {
        int l = 1, r = x;
        int mid = 0;
        while(l <= r) {
            mid = l + (r-l)/2;
            //if(mid*mid == x)
            if(mid == x/mid)//防止溢出
                return mid;
            else if(mid < x/mid)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }*/
};